In the International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) Moving Picture Experts Group-4 (MPEG-4) Part 10 Advanced Video Coding (AVC) standard/International Telecommunication Union, Telecommunication Sector (ITU-T) H.264 recommendation (hereinafter the “MPEG-4 AVC Standard”), inter-coded 16×16 pixel macroblocks may be broken into macroblock partitions, of sizes 16×8, 8×16, or 8×8. Macroblock partitions of 8×8 pixels are also known as sub-macroblocks. Sub-macroblocks may be further broken into sub-macroblock partitions, of sizes 8×4, 4×8, and 4×4. An encoder may select how to divide the macroblock into partitions and sub-macroblock partitions based on the characteristics of a particular macroblock, in order to maximize compression efficiency and subjective quality.
Furthermore, the MPEG-4 AVC Standard also supports INTRA, SKIP and DIRECT modes. Intra modes allow three types: INTRA4×4, INTRA16×16, and INTRA8×8 which is a Fidelity Range extensions mode only. INTRA4×4 and INTRA8×8 support 9 prediction modes: vertical; horizontal; DC, diagonal down/left; diagonal down/right; vertical-left; horizontal-down; vertical-right; and horizontal-up prediction. INTRA16×16 supports 4 prediction modes: vertical; horizontal; DC; and plane prediction.
As for mode decision, intra pictures should support intra modes, while inter pictures should support both inter and intra modes. Intra modes include INTRA4×4 and INTRA16×16. For P pictures, inter modes include SKIP and 16×16, 16×8, 8×16 and sub-macroblock 8×8 partitions. 8×8 further supports 8×8, 8×4, 4×8 and 4×4 partitions. For B pictures, consideration of both list 0 and list 1 and DIRECT mode are also considered for both macroblocks and sub-macroblocks.
In the prior art, a Rate-Distortion Optimization (RDO) framework is used for mode decision, i.e., an RDcost J=D+λR is used to measure the coding cost where D represents distortion and R represents the rate. For inter modes, motion estimation is separately considered from mode decision. Motion estimation is first performed for all block types of inter modes, then the mode decision is made by comparing the cost of each inter mode and intra mode. The mode with the minimal cost is selected as the best mode.
A conventional procedure to encode one macroblock s in a P- or B-picture (hereinafter the “conventional macroblock encoding procedure”) is summarized as follows.
In a first step of the conventional macroblock encoding procedure, given the last decoded pictures, we decide the Lagrangian multiplier λMODE, λMOTION, and the macroblock quantizer QP.
In a second step of the conventional macroblock encoding procedure, motion estimation and reference picture selection are performed by minimizingJ(REF,m(REF)|λMOTION)=SA(T)D(s,c(REF,m(REF)))+λMOTION(R(m(REF)−p(REF))+R(REF))for each reference picture and motion vector of a possible macroblock mode. In the preceding equation, J denotes the rate-distortion cost, REF denotes the reference picture, m denotes the current motion vector being considered, λMOTION denotes the Lagrangian multiplier, c(REF,m(REF)) denotes the compensation operation using reference REF with motion vector m, p denotes the motion vector used for the prediction during motion vector coding, R(m−p) denotes the bits used for coding the motion vector and R(REF) denotes the bits for coding the reference picture. SAD denotes the Sum of Absolute Differences between the original signal and the reference signal predicted by the motion vector.
In a third step of the conventional macroblock encoding procedure, the macroblock prediction mode is chosen by minimizingJ(s,c,MODE|QP,λMODE)=SSD(s,c,MODE|QP)+λMODE·R(s,c,MODE|QP),given QP and λMODE when varying MODE. SSD denotes the Sum of Square Differences between the original signal and the reconstructed signal. R(s,c,MODE) denotes the number of bits associated with choosing MODE, including the bits for the macroblock header, the motion and all DCT coefficients. MODE indicates a mode out of the set of potential macroblock modes, as follows:
            P      ⁢              -            ⁢      frame      ⁢              :            ⁢                          ⁢      MODE        ∈          {                                                                                                                              INTRA                      ⁢                                                                                          ⁢                      4                      ×                      4                                        ,                                          INTRA                      ⁢                                                                                          ⁢                      16                      ×                      16                                        ,                                                                                                                                          INTRA                      ⁢                                                                                          ⁢                      8                      ×                      8                                        ,                                                                                  ⁢                    SKIP                    ,                                                                                                                                                                                                      16                      ×                      16                                        ,                                          16                      ×                      8                                        ,                                          8                      ×                      16                                        ,                                          8                      ×                      8                                        ,                                                                                                                                          8                      ×                      4                                        ,                                          4                      ×                      8                                        ,                                          4                      ×                      4                                                                                                              }        ,          ⁢            B      ⁢              -            ⁢      frame      ⁢              :            ⁢                          ⁢      MODE        ∈          {                                                                  INTRA                ⁢                                                                  ⁢                4                ×                4                            ,                              INTRA                ⁢                                                                  ⁢                16                ×                16                            ,                              INTRA                ⁢                                                                  ⁢                8                ×                8                            ,                                                                          BIDIRECT              ,              DIRECT              ,                              FWD                ⁢                                                                  ⁢                16                ×                16                            ,                                                                                          FWD                ⁢                                                                  ⁢                16                ×                8                            ,                              FWD                ⁢                                                                  ⁢                8                ×                16                            ,                              FWD                ⁢                                                                  ⁢                8                ×                8                            ,                                                                                          FWD                ⁢                                                                  ⁢                8                ×                4                            ,                              FWD                ⁢                                                                  ⁢                4                ×                8                            ,                              FWD                ⁢                                                                  ⁢                4                ×                4                            ,                                                                                                                                                      BAK                      ⁢                                                                                          ⁢                      16                      ×                      16                                        ,                                          BAK                      ⁢                                                                                          ⁢                      16                      ×                      8                                        ,                                          BAK                      ⁢                                                                                          ⁢                      8                      ×                      16                                        ,                                                                                                                                          BAK                      ⁢                                                                                          ⁢                      8                      ×                      8                                        ,                                          BAK                      ⁢                                                                                          ⁢                      8                      ×                      4                                        ,                                          BAK                      ⁢                                                                                          ⁢                      4                      ×                      8                                        ,                                          BAK                      ⁢                                                                                          ⁢                      4                      ×                      4                                                                                                              }      
INTRA4×4 includes modes:
  MODE  ∈      {                                        vertical            ,            horizontal            ,                          D              ⁢                                                          ⁢              C                        ,                          diagonal              ⁢                              -                            ⁢              down              ⁢                              /                            ⁢              left                        ,                                                                          diagonal              ⁢                              -                            ⁢              down              ⁢                              /                            ⁢              right                        ,                          vertical              ⁢                              -                            ⁢              left                        ,                                                                          horizontal              ⁢                              -                            ⁢              down                        ,                          vertical              ⁢                              -                            ⁢              right                        ,                          horizontal              ⁢                              -                            ⁢              up                                            }  
INTRA16×16/INTRA8×8 include modes:                MODE ε {vertical, horizontal, DC, plane}        
Frame partitioning is a process of key importance in efficient video coding. Recent video compression technologies such as the MPEG-4 AVC Standard use a tree-based frame partition. This seems to be more efficient than a simple uniform block partition, typically used in older video coding standards and recommendations such as the International Organization for Standardization/International Electrotechnical Commission (ISO/IEC) Moving Picture Experts Group-2 (MPEG-2) Standard and the International Telecommunication Union, Telecommunication Sector (ITU-T) H.263 Recommendation (hereinafter the “H.263 Recommendation”). However, tree-based frame partitioning still does not code the video information as efficiently as possible, as it is unable to efficiently capture the geometric structure of two-dimensional (2D) data.
Inter and Intra prediction using geometric region partitioning has been identified as a promising research direction on improving video coding efficiency. Previously, for advanced video coding (such as that performed in accordance with the MPEG-4 AVC Standard), it has been proposed to introduce a geometric partition for inter and intra prediction to improve video coding efficiency. To get the best performance, it is critical for the encoder to find the optimal geometric partition. A brute-force full search strategy is used in these proposals, but the complexity is very high. However, it is desirable to have some fast algorithms for mode/partition selection so the increased computational complexity for geometric partition does not become an obstacle to the practical system.
Previously proposed was a fast algorithm developed based on edge detection in order to pre-select candidate partition lines for inter geometric mode. This fast algorithm is based on the assumption that geometric partitioning for motion compensation is expected to work better for blocks that fall along object boundaries. Up to some extent, it is reasonable to assume that pre-selecting partitions based on the image edges may achieve satisfactory results. The main disadvantage of this approach is that it is fully driven by very simple statistics and ad-hoc modeling. This results in only a part of the possible situations where geometric partitioning is useful to be actually considered, thus achieving sub-optimal results in terms of complexity savings and compression savings. Indeed, the authors of this fast algorithm assume that partitions are only related with explicit image edges. However, this is not necessarily true. For example, for an inter prediction case, partitions reflect motion boundaries rather than image edges. In some cases, image edges can coincide with motion boundaries, but not in all cases. Hence, this fast algorithm may cause a big drop in coding efficiency compared to the full search algorithm.